package com.zjs.niuke;

// 给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。
//
//        数据范围： n\leq1000n≤1000
//        要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
//
//        如当输入链表{1,2,3}时，
//        经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
public class 反转链表 {

    public static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public static class Solution {
        public ListNode ReverseList(ListNode head) {
            ListNode last = null;
            ListNode next = null;
            while (null != head) {
                next = head.next;
                head.next = last;
                last = head;
                if (null == next) {
                    break;
                }
                head = next;
            }
            return head;
        }
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        ListNode listNode = new Solution().ReverseList(listNode1);
        while (null != listNode) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}
